package com.algorithm.dm.kmean;

import java.util.ArrayList;
import java.util.List;

public class KMean<T extends Object> {
	int clusterCount;
	int maxIter;
	Distanceable disHandler;
	Centerable cenHandler;
	List<T> objs;
	Cluster[] oldClusters;
	Cluster[] clusters;

	/**
	 * 
	 * @param c 聚类个数
	 * @param m 最大迭代次数
	 * @param dis 距离计算工具
	 * @param cen 中心点计算工具
	 * @param os 要聚类的原始数据
	 */
	public KMean(int c, int m, Distanceable dis, Centerable cen, List<T> os) {
		clusterCount = c;
		maxIter = m;
		disHandler = dis;
		cenHandler = cen;
		objs = os;
	}

	/**
	 * 聚类
	 * @throws Exception
	 */
	public void cluster() throws Exception {
		if (clusterCount <= 1) {
			throw new Exception("cluster size is invalid");
		}
		if (objs.size() < clusterCount) {
			throw new Exception("data size is less than cluster size");
		}

		// 初始化clusteres个中心点
		initCenter();

		// 迭代
		int iter = 0;
		while (iter++ < maxIter) {
			saveLast();
			iter();
			if (complate()) {
				break;
			}
		}
	}

	/**
	 * 获取聚类的结果
	 * @return
	 */
	public Cluster[] result() {
		return clusters;
	}

	protected void saveLast() {
		oldClusters = clusters;
		clusters = new Cluster[clusterCount];
		for (int i = 0; i < clusterCount; i++) {
			clusters[i] = new Cluster();
		}
	}

	protected void initCenter() {
		clusters = new Cluster[clusterCount];
		for (int i = 0; i < clusterCount; i++) {
			clusters[i] = new Cluster();
			clusters[i].c = objs.get(i);
		}
	}

	protected void iter() {
		// 生成新的聚类		
		for (int i = 0; i < objs.size(); i++) { 
				Object obj =  objs.get(i);
				double min = Double.MAX_VALUE;
				int cluster = 0;

				for (int j = 0; j < clusterCount; j++) {
					double dis = disHandler.distance(oldClusters[j].c, obj);
					if (dis < min) {
						cluster = j;
						min = dis;
					}
				} 
				clusters[cluster].add(obj, min); 
		}

		// 重新計算中心點
		for (int i = 0; i < clusterCount; i++) {
			clusters[i].c = cenHandler.center(clusters[i].objs);
		}
	}

	protected boolean complate() {
		for (int i = 0; i < clusterCount; i++) {
			if (!clusters[i].c.equals(oldClusters[i].c)) {
				return false;
			}
		}
		return true;
	}

	public static interface Distanceable {
		public double distance(Object obj1, Object obj2);
	}

	public static interface Centerable {
		public Object center(List<Object> objs);
	}

	public static class Cluster {
		Object c;
		List<Object> objs;
		List<Double> dises;
		
		public Cluster() {
			objs = new ArrayList<Object>();
			dises = new ArrayList<Double>();
		}

		public void add(Object obj, double score) {
			objs.add(obj);
			dises.add(score);
		}

		public int size() {
			return objs.size();
		}
		
		public String toString() {
			StringBuilder sb= new StringBuilder();
			sb.append(c);
			sb.append("  <");
			for (int i=0;i<objs.size();i++) {
				sb.append(objs.get(i));
				if (i < objs.size() - 1) {
					sb.append(",");
				}
			}
			sb.append(">");
			return sb.toString();
		}

	}
}
